COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a52.tex[154,phy] \today\hfill}

\bigskip

\line{\bf Homework - CS 254 - to be exercises or examples.\hfil}

\medskip
\display 38pt:{\bf 1.}:
{\bf A.}\xskip
Prove that, if $M$ is a GSM with input-output relation~$R↓M$, there is a
number~$n$ for which every pair of strings $x$, $y$ for which $|x|≥n$,
$|y|≥n$, $xR↓My$, can be broken up as $x=x↓1x↓2x↓3$, $y=y↓1y↓2y↓3$,
with $|x↓2|≥1$, $|y↓2|≥1$, and $x↓1x↓2↑ix↓3\,R↓M\,y↓1y↓2↑iy↓3$ for all
$i≥0$. 

\smallskip
\display 38pt::
{\bf B.}\xskip
Can it also be required that $|x↓1x↓2|≤n$ and $|y↓1y↓2|≤n$?

\medskip
\display 38pt:{\bf 2.}:
A {\sl queue\/} is a memory device that, like a stack, holds a string;
it differs in that characters are pushed on one (say, the right) end and
popped off the other (left) end. Show that any program for a machine
with a tape, or two stacks, or two counters (your choice) can be translated
into a program for a machine with one queue as its only memory device.

\bigskip
\line{\bf Solutions\hfil}

\medskip
\display 38pt:{\bf 1.}:
{\bf A.}\xskip
Let $a$ be the length of the longest input or output of any transition,
and $b$ be the number of states of~$M$. Take $xR↓My$, where $|x|$ and
$|y|≥n=(2b+1)a$. Suppose, without loss of generality, that the computation
reads $ab$ characters before it writes $ab$ characters. Then there is an
initial portion that reads at least $ab$ characters in a least $b$~separate
transitions (writing at most $a(b+1)$ characters), and a following portion
that writes at least $ab$ characters in at least $b$~separate transitions.
States must be repeated in both portions, so

\bigskip
$$\vbox{\offinterlineskip
\halign{\hfil$#$\quad
&\hfil$#$\hfil%\vrule
&\quad\hfil$#$\hfil\quad%
&\hfil$#$\hfil%\vrule
&\xskip\hfil$#$\hfil\xskip%
&\hfil$#$\hfil\quad%\vrule
&\hfil$#$\hfil%
&\quad\hfil$#$\hfil%\vrule
&\xskip\hfil$#$\hfil\xskip%
&\hfil$#$\hfil%\vrule
&\quad\hfil$#$\hfil\quad%
&\hfil$#$\hfil\cr%\vrule
&&\multispan4\hfil\hbox{First portion}\hfil&&\multispan5\hfil\hbox{Second 
portion}\hfil\cr
%&\multispan5$\overbrace$&&\multispan5$\overbrace$\cr
\noalign{\bigskip}
&\multispan{11}\hrulefill\cr
x=&\vrule&x↓1&\vrule&x↓2≠\epsilon&\vrule&x↓3&\vrule&x↓4&\vrule&x↓5&\vrule\cr
&\multispan{11}\hrulefill\cr
\noalign{\medskip}
&&&q↓i&&q↓i&&q↓j&&q↓j\cr
\noalign{\smallskip}
&\multispan{11}\hrulefill\cr
y=&\vrule&y↓1&\vrule&y↓2&\vrule&y↓3&\vrule&y↓4≠\epsilon&\vrule&y↓5&\vrule\cr
&\multispan{11}\hrulefill\cr
}}$$

\bigskip
\disleft 38pt::
the computation can be broken into five segments as shown above, with repeated
states. Three cases arise:

\display 50pt:$\bullet$:
$y↓2≠\epsilon$; then $x↓1x↓2↑kx↓3x↓4x↓5\,R↓M\,y↓1y↓2↑ky↓3y↓4y↓5$.

\display 50pt:$\bullet$:
$x↓4≠\epsilon$; then $x↓1x↓2x↓3x↓4↑kx↓5\,R↓M\,y↓1y↓2y↓3y↓4↑ky↓5$.

\display 50pt:$\bullet$:
$x↓4=y↓2=\epsilon$; then $x↓1x↓2↑kx↓3x↓5\,R↓M\,y↓1y↓3y↓4↑ky↓5$.

\medskip
\display 38pt:{\bf 1.}:
{\bf B.}\xskip
No. See figure.

$$\offinterlineskip
\vcenter{\halign{$#$\hfil\qquad&\hfil$#$\hfil&\hfil$#$\hfil\qquad&\hfil$#$\hfil%
&\hfil$#$\hfil\cr
&a/\epsilon&&b/c\cr
\noalign{\bigskip}
&&\epsilon/\epsilon&&\epsilon/\epsilon\cr
\noalign{\smallskip}
\Rightarrow\cr}}$$

\disleft 38pt::
The strings $x=a↑ib↑i$, $y=c↑i$ are all pumpable, but only by pumping~$b$'s
and~$c$'s, and the $b$'s come after an unlimited number of~$a$'s.

\medskip
\display 38pt:{\bf 2.}:
It is known that any program for a machine with a tape, as two stacks,
can be translated into a program for a two counter machine. A~program
for a two-counter machine can be translated into a program for a one-queue
machine if we represent the first counter by the number of~1's, and the
second counter by the number of~2's, on the queue. We add one to a counter
by appending~1's or~2's to the queue. We check whether either counter is
zero by appending a~3 to the queue, cycling characters from the head to the
tail of the queue until the~3 comes off, and remembering in the control
whether a~1 (or~2) has been seen. We subtract one from either counter
by cycling characters from head to tail until a~1 (or~2) is found and removed.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 23, 1986.
%revised date;
%subsequently revised.

\bye